#include <stdio.h>
#include <stdlib.h>

typedef int HElemSet;
typedef struct SkewHeapNode *SkewHeap;
struct SkewHeapNode {
    HElemSet key; /* 数据元素 */
    SkewHeap left; /* 左子树 */
    SkewHeap right; /* 右子树 */
};

/* 算法6-10：斜堆的合并操作 SkewMerge(h1, h2) */
SkewHeap SkewMerge(SkewHeap h1, SkewHeap h2) {
    SkewHeap tmp;

    if (h1 == NULL) {
        return h2;
    }
    if (h2 == NULL) {
        return h1;
    }
    if (h1->key > h2->key) {
        return SkewMerge(h2, h1);
    }
    /* 现在 h1->key <= h2->key */
    h1->right = SkewMerge(h1->right, h2);
    tmp = h1->left;
    h1->left = h1->right;
    h1->right = tmp;
    return h1;
}
/* 算法6-10 结束 */

SkewHeap CreateNode() {
    /* 创建单个结点 */
    SkewHeap h;

    h = (SkewHeap)malloc(sizeof(struct SkewHeapNode));
    scanf("%d", &h->key);
    h->left = NULL;
    h->right = NULL;
    return h;
}

SkewHeap CreateHeap() {
    /* 创建斜堆 */
    SkewHeap h1, h2;
    int n, i;

    scanf("%d", &n);
    h1 = CreateNode();
    for (i = 1; i < n; i++) {
        h2 = CreateNode();
        h1 = SkewMerge(h1, h2); /* 将每个结点顺次并入斜堆 */
    }
    return h1;
}

void Visit(SkewHeap tree) {
    /* 输出键值和 */
    printf("%d\n", tree->key);
}

void PreOrder(SkewHeap tree) {
    /* 前序遍历 */
    if (tree != NULL) {
        Visit(tree);
        PreOrder(tree->left);
        PreOrder(tree->right);
    }
}

void InOrder(SkewHeap tree) {
    /* 中序遍历 */
    if (tree != NULL) {
        InOrder(tree->left);
        Visit(tree);
        InOrder(tree->right);
    }
}

int main(void) {
    SkewHeap h1, h2;

    h1 = CreateHeap();
    h2 = CreateHeap();
    h1 = SkewMerge(h1, h2);
    PreOrder(h1);
    InOrder(h1);

    return 0;
}